#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
 
vector<int> find_long_inc_subseq(vector<int> &seq) {
	unordered_map<int, vector<int>> ht;
 
	for(int i = 0; i < seq.size(); i++) {
		vector<int> subseq;
 
		if(i > 0) {
			int max_index = 0;
			int max_size = 0;
			int index_start = i - 1;
			bool smaller_sub_seq_found = false;
 
			for(int j = 0; j < ht.size(); j++) {
				auto it = ht.find(index_start);
 
				if(it->second.back() < seq[i] && it->second.size() > max_size) {
					smaller_sub_seq_found = true;
					max_size = it->second.size();
					max_index = index_start;
				}
 
				index_start--;
			}
 
			if(smaller_sub_seq_found) {
				auto it = ht.find(max_index);
				for(auto it2 = it->second.begin(); it2 != it->second.end(); it2++) {
					subseq.push_back(*it2);
				}
			}
		}
 
		subseq.push_back(seq[i]);
		ht.insert(make_pair(i, subseq));
	}
 
	int max_index = 0;
	int max_size = 0;
	for(int i = 0; i < ht.size(); i++) {
		auto it = ht.find(i);
 
		if(it->second.size() > max_size) {
			max_size = it->second.size();
			max_index = i;
		}
	}
	return ht.find(max_index)->second;
}
 
int find_next_larger_element(vector<vector<int>> &active_list, int num) {
	vector<int> last_elements;
	int l = 0;
	int r = 0;
 
	for(int i = 0; i <  active_list.size() - 1; i++) {
		auto it = active_list[i].back();
		last_elements.push_back(it);
	}
 
	r = last_elements.size() - 1;
 
	while(l < r) {
		int mid = l + (r - l) / 2;
 
		if (last_elements[mid] <= num) {
        /* This index, and everything below it, must not be the first element
         * greater than what we're looking for because this element is no greater
         * than the element.
         */
        	l = mid + 1;
    	}
    	else {
        	/* This element is at least as large as the element, so anything after it can't
         	 * be the first element that's at least as large.
         	 */
        	r = mid;
    	}
	}
 
	return r;
}
 
void duplicate_vector_add_element(vector<vector<int>> &active_list, int index, int element, bool replace, int insert_pos) {
	vector<int> vec;
	vec.insert(vec.begin(), active_list[index].begin(), active_list[index].end());
 
	if(!replace) {
		vec.push_back(element);
	}	
	else {
		// replace last element
		vec[vec.size() - 1] = element;
	}
 
	active_list.insert(active_list.begin() + insert_pos, vec);
}
 
vector<int> find_long_inc_subseq2(vector<int> &seq) {
	vector<vector<int>> active_list;
	bool init = true;
 
	for(int i = 0; i < seq.size(); i++) {
		if(init) {
			init = false;
 
			vector<int> vec;
			vec.push_back(seq[i]);
			active_list.push_back(vec);
		}
		else {
			auto it_first = active_list[0].back();
			auto it_last = active_list[active_list.size() - 1].back();
 
			if(seq[i] < it_first) {
				it_first = seq[i];
			}
			else if(seq[i] > it_last) {
				duplicate_vector_add_element(active_list, active_list.size() - 1, seq[i], false, active_list.size());
			}
			else {
				int index = find_next_larger_element(active_list, seq[i]);
 
				if(active_list[index].back() > seq[i]) {
					//vector<int> vec;
					//vec.insert(vec.begin(), active_list[index].begin(), active_list[index].end());
					// replace last element
					//vec[vec.size() - 1] = seq[i];
 
					active_list[index].erase(active_list[index].begin(), active_list[index].end());
					//active_list[index].insert(active_list[index].begin(), vec.begin(), vec.end());
 
					duplicate_vector_add_element(active_list, index, seq[i], true, index);
				}
				else if(active_list[index].back() < seq[i]) {
					vector<int> vec;
					vec.insert(vec.begin(), active_list[index].begin(), active_list[index].end());
					vec.push_back(seq[i]);
 
					active_list[index+1].erase(active_list[index+1].begin(), active_list[index+1].end());
					active_list[index+1].insert(active_list[index+1].begin(), vec.begin(), vec.end());
				}
			}
		}
	}
 
	return active_list[active_list.size() - 1];
}
 
int main() {
	// your code goes here
 
	vector<int> seq =  {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
	vector<int> long_sub_seq = find_long_inc_subseq2(seq);
 
	for_each(long_sub_seq.begin(), long_sub_seq.end(), [](int val) { cout << val << ' '; });
	cout << '\n';
 
	return 0;
}
